In telecommunication switching, time-division multiplex switching is commonly implemented. In such a system, a plurality of ingress ports provide a switch with grains containing data, and the received grains are multiplexed to one or more egress ports. The multiplexing of grains from ingress to egress ports is commonly done using a fixed mapping. Such time division multiplexed switches are commonly used to cross-connect lower rate signals (grains) that are contained within a higher rate signal, also referred to as a grain group. A grain group is composed of a fixed number of grains. In a standard synchronous optical network (SONET) based STS-48 channel carrying a VT1.5 virtual tributary, for example, each VT1.5 is a grain and the 1344 VT1.5s in the channel form a grain group.
FIG. 1 illustrates a plurality of data channels, received by ports A through N. Each port receives grain groups 100 containing G grains, one such grain being labelled as 102. Each grain 102 may be associated with an independent client and has a fixed location within the grain group 100. The entire grain group 100 is presented once every G clock cycles. Clock cycles are often referred to as timeslots, the use of either term should be considered interchangeable. An individual datum from a given client is available at each occurrence of the associated grain 102. The grain groups 100 in all the ports are shown to be aligned. This is a common requirement in TDM switches. In SONET switches, for example, an external alignment signal, which provides timing to the SONET transport frame or the tributary multi-frame, is used to align the grain groups.
FIG. 2 illustrates the general architecture of a TDM switch. In general, the switch has a number of inputs and number of outputs. Data grains 102 received by ingress ports (not shown) are ordered as ingress grain groups 100. The grains 102 are multiplexed by the switch 104 and transmitted by the egress ports (not shown) ordered as egress grain groups 106. For illustrative purposes, the switching system illustrated in FIG. 2 has N inputs and N outputs (N×N), but one skilled in the art will appreciate that a similar architecture can be implemented for asymmetrical switches. In FIG. 2, grains 102 are labelled with a letter representing the input port and a number (ranging from 1 to G, the number of grains in the ingress grain group 100) representing the byte position at the port. As can be seen in the output, bytes may be reordered to any position, may be multicast to several ports (or a single port), or may be dropped. FIG. 2 shows switching of grains within one grain group. The same switching of grains is performed at all recurrences of the grain groups.
FIG. 3 illustrates the conceptual implementation of an N×N memory switch 104. Two memories, 108a and 108b, are typically employed, each memory having N write ports 110 and N read ports 112. Two memories are used so that ingress ports can write a grain group to one memory using write ports 110 while the egress ports read a grain group from the other memory using read ports 112. The specific memory written to or read from alternates every grain group. The ingress ports write data into memory at an address that is indexed by the ingress port and timeslot numbers of the ingress grain. Egress ports read data from the address required to select the desired ingress grain thereby achieving the switching of ingress data to egress ports. The read address of the egress ports is defined by a connection memory that is configured by the user.
FIG. 4 illustrates the above described method of multiplexing grains from the ingress ports to egress ports. The switch receives a grain as part of a grain group at each of the ingress ports in step 114. These grains are buffered in a memory in step 116. In many implementations, the memory is sized to store one grain group from each of the ingress ports. The process of receiving and buffering grains is repeated until it has been determined that the last grain in a grain group has been received as shown in step 118. When the last grain in a grain group has been received, as determined in step 118, the process effectively forks. In the first fork, the memory bank used to buffer incoming grains in switched in step 120. In the second path of the fork, the memory bank that was just filled with incoming grains is used to multiplex out the received grains in step 122. This reading of the grains preferably takes no more than the amount of time required to fill a memory bank. The completely read out memory bank is then switched for a full memory bank in step 124. If the filling of a memory bank and the reading out a memory bank are timed properly, the process can repeat without a delay. The TDM switch will alternate between memory banks, so that as one memory bank is filled, via steps 114 and 116, the other is emptied via step 122. The memory banks are then switched in steps 120 and 124, preferably simultaneously.
It is common for switches to have a plurality of ingress and egress ports, though, using current technology, it is not practical to build fast memories with more than 3 or 4 ports. Generally, building a switch with multiple ingress and egress ports requires a slightly different architecture than the simplified illustration of FIG. 3. Two of the most common implementations are the flip-flop-based implementation illustrated in FIG. 5 and the RAM-based implementation illustrated in FIG. 6. Both these implementations make use of dual memory banks, and have an operating method similar to that illustrated in FIG. 4.
The flip-flop based implementation of an N×N memory switch, as illustrated in FIG. 5, works in two steps. First, the switch buffers all the incoming grains, received on ingress ports 110, in flip-flops, one of which is labelled 126. After receiving a full grain group, the grains are multiplexed out onto the egress ports 112. The multiplexing is performed according to the connection memory configuration 130 and requires a wide NG:1 multiplexer 128 per memory bank. Double buffering is employed to store one set of ingress grains while the other set is being multiplexed out. This implementation requires G flipflop storage elements 126 and a wide NG:1 multiplexer 128 for each egress port 112. The order of the area cost of a flip-flop based N×N memory switch is governed by the following equations:Area CostN×N=AreaFF+AreaMUX  (1.1)Area CostN×N=Order (NG)+Order (N2G log2(NG))  (1.2)
Where N=number of ports                G=number of grains in a grain group        
The random access memory (RAM) based implementation of an N×N memory switch works with the same two operational steps. First, the switch buffers all the incoming grains, received on the ingress ports 110, in RAMs, one of which is labelled 132. It then multiplexes the grains out onto the egress ports 112 according to the connection memory configuration 130. Double buffering is employed to store one set of ingress grains while the other set is being multiplexed out. The main difference from the flip-flop based implementation is all the ingress grains are stored in RAMs 132 instead of flip-flops. A RAM is more area efficient, but only one grain can be accessed at a time. Consequently, each ingress grain must be stored on a per egress port basis rather then on a per switch basis. Thus, the RAM based implementation minimizes the width of the egress multiplexer 134 to N:1 per egress port but requires NG storage elements 132 per egress port. The order of the area cost of a memory based N×N memory switch is governed by the following equations:Area CostN×N=AreaRAM+AreaMUX  (2.1)Area CostN×N=Order(N2G)+Order(N2 log2(N))  (2.2)
Where N=number of ports                G=number of grains in a grain group        
Telecommunication systems typically have a maximum physical area and cost budget for printed circuit boards. Minimizing the physical area and cost of a printed circuit boards allows network equipment vendors to minimize equipment cost in order to gain market share. Since both physical area and cost are derived from both the number and physical dimension of integrated components, reducing the number and size of those components will have a positive effect on both the physical area and cost of the printed circuit board. In particular, memory switch area grows with switch capacity, thus it is important to reduce area in switching components to enable the design of large switching systems with a minimal number of components.
Both the implementation of FIG. 5 and the implementation of FIG. 6 consist of a memory to store ingress grains for subsequent output to the egress ports and multiplexing logic to select the desired ingress grain. The area costs for these implementations are defined above in equations 1.1, 1.2, 2.1 and 2.2.
In the flip-flop based implementation of FIG. 5, where a wide NG:1 multiplexer per egress port is required, the multiplexer is able to select NG ingress grains but only G ingress grains are selected per egress port. This results in a sub-optimal utilization of the dedicated resources. The following equations give the utilization percentage of the egress multiplexer in a flip-flop based implementation of an N×N memory switch as illustrated in FIG. 5.Utilization %N×N=[Tot egress mux−Inactive egress mux]/[Tot egress mux]  (3.1)Utilization %N×N=[N2G log2(NG)−N(N−1)G log2((N−1)G)]/[N2G log2(NG)]  (3.2)
Where N=number of ports                G=number of grains in a grain group        
For N=18 and G=1344 Utilization % N×N=6.1%
(i.e. 45G SONET/SDH VT/TU cross connect)
In the RAM based implementation of FIG. 6 which requires N RAMs per egress port, the RAMs hold NG ingress grains but only G ingress grains are read out per egress port. The area is not optimal with respect to the storage element. The following equations gives the utilization percentage of the storage element in a RAM based implementation of an N×N memory switch.Utilization %N×N=[Tot storage−Unused storage]/[Tot storage]  (4.1)Utilization %N×N=[N2G−N(N−1)G]/[N2G]  (4.2)Utilization %N×N=1/N  (4.3)
Where N=number of ports                G=number of grains in a grain group        
For N=18 and G=1344 Utilization % N×N=5.5%
(i.e. 45G SONET/SDH VT/TU cross connect)
Though the RAM and flip-flop architectures allow for multiplexing the grains received by the ingress ports to the egress ports in a time efficient manner, their space consumption requires large implementations in chips and on printed circuit boards. These two factors increase their cost. The large implementation area is related to the poor utilization of multiplexing capacity and RAM storage. It is, therefore, desirable to provide a multiplexing egress structure that reduces the implementation size and increases the utilization percentage.